package bin_tree.heap;

import java.awt.*;
import java.util.ArrayList;
import java.util.List;

/**
 * 基于数组实现的最大堆
 * 编号从0开始，编号对应数组的下标index,index>0;
 * 父节点=index-1/2
 * 若有左右孩子，保证2*index+1或2*index+2<data.length
 * 左孩子=2*index+1  右孩子=2*index+2
 */
public class MaxHeap {
    private ArrayList<Integer> data;
    public MaxHeap() {
        data=new ArrayList<>();
    }
    public MaxHeap(int capacity){
        data=new ArrayList<>(capacity);
    }

    //heapify
    public MaxHeap(int[] arr){
        data=new ArrayList<>(arr.length);
        for (int i:arr) {
            data.add(i);
        }
        for (int i =parent(data.size()-1) ; i >=0; i--) {
            siftDown(i);
        }
    }
    public boolean isEmpty(){
        return data.size()==0;
    }

    //三个私有方法
    //获取父节点的索引
    private int parent(int k){
        return (k-1)/2;
    }
    //获取左孩子的索引
    private int left(int k){
        return  2*k+1;
    }
    //获取右孩子的索引
    private int right(int k){
        return 2*k+2;
    }

    //增删改查
    //增加元素 上浮操作
    public void add(int val){
        data.add(val);
        siftUp(data.size()-1);
    }

    /**
     * 取出当前堆的最大值 
     * 继续调整当前堆，使其满足堆的节点性质
     */
    public int  extractMax(){
        if(isEmpty()){
            System.out.println("heap is empty!");
        }
        int max=data.get(0);
        data.set(0,data.get(data.size()-1));
        data.remove(data.size()-1);
        siftDown(0);
        return max;
    }


    /**
     * 元素的上浮操作
     * @param i 当前要上浮的元素下标
     */
    private void siftUp(int i) {
        while (i > 0 && data.get(i) > data.get(parent(i))) {
            swap(i, parent(i));
            //继续向上判断i是否需要交换
            i = parent(i);
        }
    }
    public int peekHeap(){
        if(data.size()==0){
            System.out.println("heap is empty!");
        }
        return data.get(0);

    }
    //交换当前数组中i和parent的值
    private void swap(int i, int parent) {
        int tmp=data.get(i);
        int parentVal=data.get(parent);
        data.set(i,parentVal);
        data.set(parent,tmp);
    }

    /**
     *元素的下沉操作
     * @param i 当前要下沉的元素下标
     */
    private void siftDown(int i) {
        //左子树存在
        while (left(i)<data.size()){
            int j=left(i);
            //右子树也存在
            if(right(i)< data.size()){
                int leftVal=data.get(left(i));
                int rightVal=data.get(right(i));
                if(leftVal<rightVal){
                    j=j+1;
                }
            }
            if(data.get(i)>=data.get(j)){
                //当前节点已经大于左右孩子，下沉结束
                break;
            }else {
                swap(i,j);
                i=j;
            }
        }
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder=new StringBuilder();
        stringBuilder.append("[");
        for (int i = 0; i < data.size(); i++) {
            stringBuilder.append(data.get(i));
            if(i!=data.size()-1){
                stringBuilder.append(",");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }
}
